package com.example.learn.hwod.并查集;

import java.util.ArrayList;
import java.util.List;

public class 全排列 {

    public static List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>(len);
        boolean[] onPath = new  boolean[len];
        dfs(0,path,onPath,res,nums);

        return res;
    }

    private static void dfs(int i, List<Integer> path, boolean[] onPath, List<List<Integer>> res, int[] nums) {
        if (i==nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int j = 0; j < nums.length; j++) {
            if(!onPath[j]){
                path.set(i,nums[j]);
                onPath[j] = true;
                dfs(i+1,path,onPath,res,nums);
                onPath[j] = false;
            }
        }
    }


    public static void main(String[] args) {

    }
}
